/*
 输入n个元素组成的序列S，你需要找出一个乘积最大的连续子序列。如果这个最大的乘积不是正数，应输出-1（表示无解）。1≤n≤18，-10≤Si≤10。
 样例输入：
 3
 2 4 -1
 5
 2 5 -1 2 -1
 样例输出：
 8
 20
 -------------------------------------------------------------------------------
 枚举起点和终点即可，由于每个元素的绝对值不超过10，一共又不超过18个元素，最大可能的乘积不会超过10^18，可以用long存储。
 */
package com.yuan.algorithms.Algorithm_2;

import java.util.Scanner;

public class 枚举_最大乘积 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] target = new int[n];
            for (int i = 0; i < n; i++) {
                target[i] = sc.nextInt();
            }
            long max = target[0];
            int Start = 0, End = 0;
            for (int i = 0; i < n; i++) {
                long temp = target[i];
                //max = temp > max ? temp : max;
                if (temp > max) {
                        max = temp;
                        Start = End = i;
                    }
                for (int j = i + 1; j < n; j++) {
                    temp *= target[j];
                    //max = temp > max ? temp : max;
                    if (temp > max) {
                        max = temp;
                        Start = i;
                        End = j;
                    }
                }
            }
            max = max < 0 ? -1 : max;
            System.out.println("Max=" + max + " Start:" + Start + " End:" + End);
        }

    }

}
